﻿// 2470. 最小公倍数为 K 的子数组数目.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>

using namespace std;

/*
https://leetcode.cn/problems/number-of-subarrays-with-lcm-equal-to-k/description/

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的 子数组 中满足 元素最小公倍数为 k 的子数组数目。

子数组 是数组中一个连续非空的元素序列。

数组的最小公倍数 是可被所有数组元素整除的最小正整数。



示例 1 ：
输入：nums = [3,6,2,7,1], k = 6
输出：4
解释：以 6 为最小公倍数的子数组是：
- [3,6,2,7,1]
- [3,6,2,7,1]
- [3,6,2,7,1]
- [3,6,2,7,1]

示例 2 ：
输入：nums = [3], k = 2
输出：0
解释：不存在以 2 为最小公倍数的子数组。


提示：

1 <= nums.length <= 1000
1 <= nums[i], k <= 1000
*/

class Solution {
public:
    int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    int subarrayLCM(vector<int>& nums, int k) {
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            int a = nums[i];
            int  lcm = a;
            if (lcm == k) {
                ans++;
                //cout << "1 i = " << i << endl;
            }
            if (lcm > k) { continue; }
            for (int j = i + 1; j < nums.size(); j++) {
                lcm = 1LL * lcm * nums[j] / gcd(lcm, nums[j]);
                if (lcm > k) { break; }
                if (lcm == k) {
                    ans++;
                    //cout << "i = " << i << ". j = " << j << endl;
                }
            }
        }

        return ans;
    }
};

//3,6,2,7,1


int main()
{
    Solution s;
    vector<int> v{ 773,613,11,8,103 };
    s.subarrayLCM(v, 40);
}

 